package com.formula.datastructure.exercise.sort.adv;

import com.formula.datastructure.util.DataUtil;

/**
 * 归并排序相对比较麻烦
 * private Integer[] temp;
 * <p>
 * public Integer[] sort(Integer[] input) {
 * temp = new Integer[input.length];
 * mergeSort(input, 0, input.length - 1);
 * return input;
 * }
 * <p>
 * private void mergeSort(Integer[] array, int low, int high) {
 * if (low < high) {
 * int mid = (low + high) / 2;
 * mergeSort(array, low, mid);
 * mergeSort(array, mid + 1, high);
 * merge(array, low, mid, high);
 * }
 * }
 * <p>
 * 先记住这段框架
 * <p>
 * 另一部分就是merge的逻辑, 现在有两个排好序的数组, 怎么把它们填入临时数组
 */
public class MergeSort {

    // 需要申明辅助数组
    private Integer[] temp;

    public Integer[] sort(Integer[] input) {
        temp = new Integer[input.length];
        mergeSort(input, 0, input.length - 1);
        return input;
    }

    private void mergeSort(Integer[] array, int low, int high) {
        // low<high 很重要
        if (low < high) {
            int mid = (low + high) / 2;
            mergeSort(array, low, mid);
            mergeSort(array, mid + 1, high);
            merge(array, low, mid, high);
        }
    }

    /**
     * 错误:
     * #1 没有赋值回去
     *
     * @param array
     * @param low
     * @param mid
     * @param high
     */
    private void merge(Integer[] array, int low, int mid, int high) {
        // 保存low的值很重要
        int left = low;
        int right = mid + 1;
        int count = 0;
        while (low <= mid && right <= high) {
            if (array[low] < array[right]) {
                temp[count++] = array[low++];
            } else {
                temp[count++] = array[right++];
            }
        }

        while (low <= mid) {
            temp[count++] = array[low++];
        }
        while (right <= high) {
            temp[count++] = array[right++];
        }


        // 这里非常重要, 必须从low开始, 不是从0
        count = 0;
        while (left <= high) {
            array[left++] = temp[count++];
        }
    }

    public static void main(String[] args) {
        MergeSort merge = new MergeSort();
        Integer[] array = DataUtil.genUniqueArray(12, 100);
        DataUtil.printIndex(12);
        DataUtil.printArray(array);
        DataUtil.printArray(merge.sort(array));
    }
}
